<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 3.1</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 3.1" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 3.1" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-3.xhtml#Chapter-3" rel="prev" title="Chapter 3" />
<link href="3_002e2.xhtml#g_t3_002e2" rel="next" title="3.2" />
<link href="Chapter-3.xhtml#Chapter-3" rel="prev" title="Chapter 3" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t3_002e1"></a>
<nav class="header">
<p>
Next: <a href="3_002e2.xhtml#g_t3_002e2" accesskey="n" rel="next">3.2</a>, Prev: <a href="Chapter-3.xhtml#Chapter-3" accesskey="p" rel="prev">Chapter 3</a>, Up: <a href="Chapter-3.xhtml#Chapter-3" accesskey="u" rel="prev">Chapter 3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Assignment-and-Local-State"></a>
<h3 class="section"><span class="secnum">3.1</span><span class="sectitle">Assignment and Local State</span></h3>

<p>We ordinarily view the world as populated by independent objects, each of which
has a state that changes over time.  An object is said to “have state” if its
behavior is influenced by its history.  A bank account, for example, has state
in that the answer to the question “Can I withdraw $100?”  depends upon the
history of deposit and withdrawal transactions.  We can characterize an
object’s state by one or more <a id="index-state-variables-1"></a>
<em>state variables</em>, which among them
maintain enough information about history to determine the object’s current
behavior.  In a simple banking system, we could characterize the state of an
account by a current balance rather than by remembering the entire history of
account transactions.
</p>
<p>In a system composed of many objects, the objects are rarely completely
independent.  Each may influence the states of others through interactions,
which serve to couple the state variables of one object to those of other
objects.  Indeed, the view that a system is composed of separate objects is
most useful when the state variables of the system can be grouped into closely
coupled subsystems that are only loosely coupled to other subsystems.
</p>
<p>This view of a system can be a powerful framework for organizing computational
models of the system.  For such a model to be modular, it should be decomposed
into computational objects that model the actual objects in the system.  Each
computational object must have its own <a id="index-local-state-variables"></a>
<em>local state variables</em>
describing the actual object’s state.  Since the states of objects in the
system being modeled change over time, the state variables of the corresponding
computational objects must also change.  If we choose to model the flow of time
in the system by the elapsed time in the computer, then we must have a way to
construct computational objects whose behaviors change as our programs run.  In
particular, if we wish to model state variables by ordinary symbolic names in
the programming language, then the language must provide an <a id="index-assignment-operator"></a>
<em>assignment operator</em> 
to enable us to change the value associated with a name.
</p>

<a id="g_t3_002e1_002e1"></a>
<a id="Local-State-Variables"></a>
<h4 class="subsection"><span class="secnum">3.1.1</span><span class="sectitle">Local State Variables</span></h4>

<p>To illustrate what we mean by having a computational object with time-varying
state, let us model the situation of withdrawing money from a bank account.  We
will do this using a procedure <code>withdraw</code>, which takes as argument an
<code>amount</code> to be withdrawn.  If there is enough money in the account to
accommodate the withdrawal, then <code>withdraw</code> should return the balance
remaining after the withdrawal.  Otherwise, <code>withdraw</code> should return the
message <em>Insufficient funds</em>. For example, if we begin with $100 in the
account, we should obtain the following sequence of responses using
<code>withdraw</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">withdraw </span><span class="lit">25</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">75</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">withdraw </span><span class="lit">25</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">50</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">withdraw </span><span class="lit">60</span><span class="clo">)</span><span class="pln">
</span><i><span class="str">"Insufficient funds"</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">withdraw </span><span class="lit">15</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">35</span></i>
</pre></div>

<p>Observe that the expression <code>(withdraw 25)</code>, evaluated twice, yields
different values.  This is a new kind of behavior for a procedure.  Until now,
all our procedures could be viewed as specifications for computing mathematical
functions.  A call to a procedure computed the value of the function applied to
the given arguments, and two calls to the same procedure with the same
arguments always produced the same result.<a class="footnote_link" id="DOCF129" href="#FOOT129"><sup>129</sup></a>
</p>
<p>To implement <code>withdraw</code>, we can use a variable <code>balance</code> to indicate
the balance of money in the account and define <code>withdraw</code> as a procedure
that accesses <code>balance</code>.  The <code>withdraw</code> procedure checks to see if
<code>balance</code> is at least as large as the requested <code>amount</code>.  If so,
<code>withdraw</code> decrements <code>balance</code> by <code>amount</code> and returns the new
value of <code>balance</code>.  Otherwise, <code>withdraw</code> returns the
<em>Insufficient funds</em> message.  Here are the definitions of <code>balance</code>
and <code>withdraw</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> balance </span><span class="lit">100</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
             balance</span><span class="clo">)</span><span class="pln">
      </span><span class="str">"Insufficient funds"</span><span class="clo">))</span></pre></div>

<p>Decrementing <code>balance</code> is accomplished by the expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span></pre></div>

<p>This uses the <code>set!</code> special form, whose syntax is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> ⟨</span><var><span class="pln">name</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">new-value</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>Here <code>⟨</code><var>name</var><code>⟩</code> is a symbol and <code>⟨</code><var>new-value</var><code>⟩</code> is any expression.
<code>Set!</code> changes <code>⟨</code><var>name</var><code>⟩</code> so that its value is the result obtained by
evaluating <code>⟨</code><var>new-value</var><code>⟩</code>.  In the case at hand, we are changing
<code>balance</code> so that its new value will be the result of subtracting
<code>amount</code> from the previous value of <code>balance</code>.<a class="footnote_link" id="DOCF130" href="#FOOT130"><sup>130</sup></a>
</p>
<p><code>Withdraw</code> also uses the <code>begin</code> special form to cause two
expressions to be evaluated in the case where the <code>if</code> test is true: first
decrementing <code>balance</code> and then returning the value of <code>balance</code>.  In
general, evaluating the expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> ⟨</span><var><span class="pln">exp</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">₂</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">exp</span><span class="pun">ₖ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>causes the expressions <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mi>e</mi>
    <mi>x</mi>
    <msub>
      <mi>p</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> through <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mi>e</mi>
    <mi>x</mi>
    <msub>
      <mi>p</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> to be evaluated
in sequence and the value of the final expression <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mi>e</mi>
    <mi>x</mi>
    <msub>
      <mi>p</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> to be
returned as the value of the entire <code>begin</code> form.<a class="footnote_link" id="DOCF131" href="#FOOT131"><sup>131</sup></a>
</p>
<p>Although <code>withdraw</code> works as desired, the variable <code>balance</code> presents
a problem.  As specified above, <code>balance</code> is a name defined in the global
environment and is freely accessible to be examined or modified by any
procedure.  It would be much better if we could somehow make <code>balance</code>
internal to <code>withdraw</code>, so that <code>withdraw</code> would be the only
procedure that could access <code>balance</code> directly and any other procedure
could access <code>balance</code> only indirectly (through calls to <code>withdraw</code>).
This would more accurately model the notion that <code>balance</code> is a local
state variable used by <code>withdraw</code> to keep track of the state of the
account.
</p>
<p>We can make <code>balance</code> internal to <code>withdraw</code> by rewriting the
definition as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> new-withdraw
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">balance </span><span class="lit">100</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                       </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
                 balance</span><span class="clo">)</span><span class="pln">
          </span><span class="str">"Insufficient funds"</span><span class="clo">))))</span></pre></div>

<p>What we have done here is use <code>let</code> to establish an environment with a
local variable <code>balance</code>, bound to the initial value 100.  Within this
local environment, we use <code>lambda</code> to create a procedure that takes
<code>amount</code> as an argument and behaves like our previous <code>withdraw</code>
procedure.  This procedure—returned as the result of evaluating the
<code>let</code> expression—is <code>new-withdraw</code>, which behaves in precisely the
same way as <code>withdraw</code> but whose variable <code>balance</code> is not accessible
by any other procedure.<a class="footnote_link" id="DOCF132" href="#FOOT132"><sup>132</sup></a>
</p>
<p>Combining <code>set!</code> with local variables is the general programming technique
we will use for constructing computational objects with local state.
Unfortunately, using this technique raises a serious problem: When we first
introduced procedures, we also introduced the substitution model of evaluation
(<a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a>) to provide an interpretation of what procedure
application means.  We said that applying a procedure should be interpreted as
evaluating the body of the procedure with the formal parameters replaced by
their values.  The trouble is that, as soon as we introduce assignment into our
language, substitution is no longer an adequate model of procedure application.
(We will see why this is so in <a href="#g_t3_002e1_002e3">3.1.3</a>.)  As a consequence, we
technically have at this point no way to understand why the <code>new-withdraw</code>
procedure behaves as claimed above.  In order to really understand a procedure
such as <code>new-withdraw</code>, we will need to develop a new model of procedure
application.  In <a href="3_002e2.xhtml#g_t3_002e2">3.2</a> we will introduce such a model, together
with an explanation of <code>set!</code> and local variables.  First, however, we
examine some variations on the theme established by <code>new-withdraw</code>.
</p>
<p>The following procedure, <code>make-withdraw</code>, creates “withdrawal
processors.”  The formal parameter <code>balance</code> in <code>make-withdraw</code>
specifies the initial amount of money in the account.<a class="footnote_link" id="DOCF133" href="#FOOT133"><sup>133</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-withdraw balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">)))</span></pre></div>

<p><code>Make-withdraw</code> can be used as follows to create two objects <code>W1</code> and
<code>W2</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W1 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W2 </span><span class="opn">(</span><span class="pln">make-withdraw </span><span class="lit">100</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">W1 </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">50</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">W2 </span><span class="lit">70</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">30</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">W2 </span><span class="lit">40</span><span class="clo">)</span><span class="pln">
</span><i><span class="str">"Insufficient funds"</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">W1 </span><span class="lit">40</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">10</span></i>
</pre></div>

<p>Observe that <code>W1</code> and <code>W2</code> are completely independent objects, each
with its own local state variable <code>balance</code>.  Withdrawals from one do not
affect the other.
</p>
<p>We can also create objects that handle deposits as well as withdrawals, and
thus we can represent simple bank accounts.  Here is a procedure that returns a
“bank-account object” with a specified initial balance:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-account balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">withdraw amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;=</span><span class="pln"> balance amount</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance 
                     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
               balance</span><span class="clo">)</span><span class="pln">
        </span><span class="str">"Insufficient funds"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deposit amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dispatch m</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> withdraw</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">eq</span><span class="pun">?</span><span class="pln"> m </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> deposit</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Unknown request: 
                 MAKE-ACCOUNT"</span><span class="pln"> m</span><span class="clo">))))</span><span class="pln">
  dispatch</span><span class="clo">)</span></pre></div>

<p>Each call to <code>make-account</code> sets up an environment with a local state
variable <code>balance</code>.  Within this environment, <code>make-account</code> defines
procedures <code>deposit</code> and <code>withdraw</code> that access <code>balance</code> and an
additional procedure <code>dispatch</code> that takes a “message” as input and
returns one of the two local procedures.  The <code>dispatch</code> procedure itself
is returned as the value that represents the bank-account object.  This is
precisely the <a id="index-message_002dpassing"></a>
<em>message-passing</em> style of programming that we saw in
<a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a>, although here we are using it in conjunction with the
ability to modify local variables.
</p>
<p><code>Make-account</code> can be used as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> acc </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="clo">))</span><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">50</span></i><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> </span><span class="lit">60</span><span class="clo">)</span><span class="pln">
</span><i><span class="str">"Insufficient funds"</span></i><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> </span><span class="lit">40</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">90</span></i><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> </span><span class="lit">60</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">30</span></i>
</pre></div>

<p>Each call to <code>acc</code> returns the locally defined <code>deposit</code> or
<code>withdraw</code> procedure, which is then applied to the specified
<code>amount</code>.  As was the case with <code>make-withdraw</code>, another call to
<code>make-account</code>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> acc2 </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>will produce a completely separate account object, which maintains its own
local <code>balance</code>.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e1"></a>Exercise 3.1:</strong> An <a id="index-accumulator-1"></a>
<em>accumulator</em> is a
procedure that is called repeatedly with a single numeric argument and
accumulates its arguments into a sum.  Each time it is called, it returns the
currently accumulated sum.  Write a procedure <code>make-accumulator</code> that
generates accumulators, each maintaining an independent sum.  The input to
<code>make-accumulator</code> should specify the initial value of the sum; for
example
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> A </span><span class="opn">(</span><span class="pln">make-accumulator </span><span class="lit">5</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">A </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">15</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">A </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">25</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e2"></a>Exercise 3.2:</strong> In software-testing applications,
it is useful to be able to count the number of times a given procedure is
called during the course of a computation.  Write a procedure
<code>make-monitored</code> that takes as input a procedure, <code>f</code>, that itself
takes one input.  The result returned by <code>make-monitored</code> is a third
procedure, say <code>mf</code>, that keeps track of the number of times it has been
called by maintaining an internal counter.  If the input to <code>mf</code> is the
special symbol <code>how-many-calls?</code>, then <code>mf</code> returns the value of the
counter.  If the input is the special symbol <code>reset-count</code>, then <code>mf</code>
resets the counter to zero.  For any other input, <code>mf</code> returns the result
of calling <code>f</code> on that input and increments the counter.  For instance, we
could make a monitored version of the <code>sqrt</code> procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> s </span><span class="opn">(</span><span class="pln">make-monitored sqrt</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">s </span><span class="lit">100</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">10</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">s </span><span class="lit">'how-many-calls?</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">1</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e3"></a>Exercise 3.3:</strong> Modify the <code>make-account</code>
procedure so that it creates password-protected accounts.  That is,
<code>make-account</code> should take a symbol as an additional argument, as in
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> acc 
  </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="pln"> </span><span class="lit">'secret-password</span><span class="clo">))</span></pre></div>

<p>The resulting account object should process a request only if it is accompanied
by the password with which the account was created, and should otherwise return
a complaint:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">acc </span><span class="lit">'secret-password</span><span class="pln"> </span><span class="lit">'withdraw</span><span class="clo">)</span><span class="pln"> </span><span class="lit">40</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">60</span></i><span class="pln">

</span><span class="opn">((</span><span class="pln">acc </span><span class="lit">'some-other-password</span><span class="pln"> </span><span class="lit">'deposit</span><span class="clo">)</span><span class="pln"> </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><i><span class="str">"Incorrect password"</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e4"></a>Exercise 3.4:</strong> Modify the <code>make-account</code>
procedure of <a href="#Exercise-3_002e3">Exercise 3.3</a> by adding another local state variable so that,
if an account is accessed more than seven consecutive times with an incorrect
password, it invokes the procedure <code>call-the-cops</code>.
</p></blockquote>

<a id="g_t3_002e1_002e2"></a>
<a id="The-Benefits-of-Introducing-Assignment"></a>
<h4 class="subsection"><span class="secnum">3.1.2</span><span class="sectitle">The Benefits of Introducing Assignment</span></h4>

<p>As we shall see, introducing assignment into our programming language leads us
into a thicket of difficult conceptual issues.  Nevertheless, viewing systems
as collections of objects with local state is a powerful technique for
maintaining a modular design.  As a simple example, consider the design of a
procedure <code>rand</code> that, whenever it is called, returns an integer chosen at
random.
</p>
<p>It is not at all clear what is meant by “chosen at random.”  What we
presumably want is for successive calls to <code>rand</code> to produce a sequence of
numbers that has statistical properties of uniform distribution.  We will not
discuss methods for generating suitable sequences here.  Rather, let us assume
that we have a procedure <code>rand-update</code> that has the property that if we
start with a given number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>x</mi>
    <mn>1</mn>
  </msub>
</math> and form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><var><span class="pln">x</span><span class="pun">₂</span></var><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rand-update </span><var><span class="pln">x</span><span class="pun">₁</span></var><span class="clo">)</span><span class="pln">
</span><var><span class="pln">x</span><span class="pun">₃</span></var><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rand-update </span><var><span class="pln">x</span><span class="pun">₂</span></var><span class="clo">)</span></pre></div>

<p>then the sequence of values <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>x</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>x</mi>
    <mn>2</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>x</mi>
    <mn>3</mn>
  </msub>
</math>, … will have the
desired statistical properties.<a class="footnote_link" id="DOCF134" href="#FOOT134"><sup>134</sup></a>
</p>
<p>We can implement <code>rand</code> as a procedure with a local state variable
<code>x</code> that is initialized to some fixed value <code>random-init</code>.  Each call
to <code>rand</code> computes <code>rand-update</code> of the current value of <code>x</code>,
returns this as the random number, and also stores this as the new value of
<code>x</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> rand
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x random-init</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">rand-update x</span><span class="clo">))</span><span class="pln"> x</span><span class="clo">)))</span></pre></div>

<p>Of course, we could generate the same sequence of random numbers without using
assignment by simply calling <code>rand-update</code> directly.  However, this would
mean that any part of our program that used random numbers would have to
explicitly remember the current value of <code>x</code> to be passed as an argument
to <code>rand-update</code>.  To realize what an annoyance this would be, consider
using random numbers to implement a technique called <a id="index-Monte-Carlo-simulation"></a>
<em>Monte Carlo simulation</em>.
</p>
<p>The Monte Carlo method consists of choosing sample experiments at random from a
large set and then making deductions on the basis of the probabilities
estimated from tabulating the results of those experiments.  For example, we
can approximate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> using the fact that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>6</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>π<!-- π --></mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math> is the probability
that two integers chosen at random will have no factors in common; that is,
that their greatest common divisor will be 1.<a class="footnote_link" id="DOCF135" href="#FOOT135"><sup>135</sup></a> To
obtain the approximation to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>, we perform a large number of experiments.
In each experiment we choose two integers at random and perform a test to see
if their <abbr>GCD</abbr> is 1.  The fraction of times that the test is passed
gives us our estimate of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>6</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>π<!-- π --></mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>, and from this we obtain our
approximation to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>.
</p>
<p>The heart of our program is a procedure <code>monte-carlo</code>, which takes as
arguments the number of times to try an experiment, together with the
experiment, represented as a no-argument procedure that will return either true
or false each time it is run.  <code>Monte-carlo</code> runs the experiment for the
designated number of trials and returns a number telling the fraction of the
trials in which the experiment was found to be true.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">estimate-pi trials</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sqrt </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> </span><span class="opn">(</span><span class="pln">monte-carlo trials 
                          cesaro-test</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cesaro-test</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd </span><span class="opn">(</span><span class="pln">rand</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rand</span><span class="clo">))</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">monte-carlo trials experiment</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter trials-remaining trials-passed</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> trials-remaining </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> trials-passed trials</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">experiment</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> trials-remaining </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> 
                 </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> trials-passed </span><span class="lit">1</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> trials-remaining </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> 
                 trials-passed</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter trials </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>Now let us try the same computation using <code>rand-update</code> directly rather
than <code>rand</code>, the way we would be forced to proceed if we did not use
assignment to model local state:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">estimate-pi trials</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sqrt </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> </span><span class="opn">(</span><span class="pln">random-gcd-test trials 
                              random-init</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">random-gcd-test trials initial-x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter trials-remaining 
                trials-passed 
                x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x1 </span><span class="opn">(</span><span class="pln">rand-update x</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x2 </span><span class="opn">(</span><span class="pln">rand-update x1</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> trials-remaining </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> trials-passed trials</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd x1 x2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> trials-remaining </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> trials-passed </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                     x2</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> trials-remaining </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                     trials-passed
                     x2</span><span class="clo">))))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter trials </span><span class="lit">0</span><span class="pln"> initial-x</span><span class="clo">))</span></pre></div>

<p>While the program is still simple, it betrays some painful breaches of
modularity.  In our first version of the program, using <code>rand</code>, we can
express the Monte Carlo method directly as a general <code>monte-carlo</code>
procedure that takes as an argument an arbitrary <code>experiment</code> procedure.
In our second version of the program, with no local state for the random-number
generator, <code>random-gcd-test</code> must explicitly manipulate the random numbers
<code>x1</code> and <code>x2</code> and recycle <code>x2</code> through the iterative loop as the
new input to <code>rand-update</code>.  This explicit handling of the random numbers
intertwines the structure of accumulating test results with the fact that our
particular experiment uses two random numbers, whereas other Monte Carlo
experiments might use one random number or three.  Even the top-level procedure
<code>estimate-pi</code> has to be concerned with supplying an initial random number.
The fact that the random-number generator’s insides are leaking out into other
parts of the program makes it difficult for us to isolate the Monte Carlo idea
so that it can be applied to other tasks.  In the first version of the program,
assignment encapsulates the state of the random-number generator within the
<code>rand</code> procedure, so that the details of random-number generation remain
independent of the rest of the program.
</p>
<p>The general phenomenon illustrated by the Monte Carlo example is this: From the
point of view of one part of a complex process, the other parts appear to
change with time.  They have hidden time-varying local state.  If we wish to
write computer programs whose structure reflects this decomposition, we make
computational objects (such as bank accounts and random-number generators)
whose behavior changes with time.  We model state with local state variables,
and we model the changes of state with assignments to those variables.
</p>
<p>It is tempting to conclude this discussion by saying that, by introducing
assignment and the technique of hiding state in local variables, we are able to
structure systems in a more modular fashion than if all state had to be
manipulated explicitly, by passing additional parameters.  Unfortunately, as we
shall see, the story is not so simple.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e5"></a>Exercise 3.5:</strong> <a id="index-Monte-Carlo-integration"></a>
<em>Monte Carlo integration</em>
is a method of estimating definite integrals by means of Monte Carlo
simulation.  Consider computing the area of a region of space described by a
predicate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>P</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> that is true for points <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> in the
region and false for points not in the region.  For example, the region
contained within a circle of radius 3 centered at (5, 7) is described by the
predicate that tests whether <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>−<!-- − --></mo>
    <mn>5</mn>
    <msup>
      <mo stretchy="false">)</mo>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>−<!-- − --></mo>
    <mn>7</mn>
    <msup>
      <mo stretchy="false">)</mo>
      <mn>2</mn>
    </msup>
    <mo>≤<!-- ≤ --></mo>
    <msup>
      <mn>3</mn>
      <mn>2</mn>
    </msup>
  </mrow>
</math>.  To estimate
the area of the region described by such a predicate, begin by choosing a
rectangle that contains the region.  For example, a rectangle with diagonally
opposite corners at (2, 4) and (8, 10) contains the circle above.  The desired
integral is the area of that portion of the rectangle that lies in the region.
We can estimate the integral by picking, at random, points <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> that
lie in the rectangle, and testing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>P</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> for each point to
determine whether the point lies in the region.  If we try this with many
points, then the fraction of points that fall in the region should give an
estimate of the proportion of the rectangle that lies in the region.  Hence,
multiplying this fraction by the area of the entire rectangle should produce an
estimate of the integral.
</p>
<p>Implement Monte Carlo integration as a procedure <code>estimate-integral</code> that
takes as arguments a predicate <code>P</code>, upper and lower bounds <code>x1</code>,
<code>x2</code>, <code>y1</code>, and <code>y2</code> for the rectangle, and the number of trials
to perform in order to produce the estimate.  Your procedure should use the
same <code>monte-carlo</code> procedure that was used above to estimate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>.
Use your <code>estimate-integral</code> to produce an estimate of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> by
measuring the area of a unit circle.
</p>
<p>You will find it useful to have a procedure that returns a number chosen at
random from a given range.  The following <code>random-in-range</code> procedure
implements this in terms of the <code>random</code> procedure used in 
<a href="1_002e2.xhtml#g_t1_002e2_002e6">1.2.6</a>, which returns a nonnegative number less than its
input.<a class="footnote_link" id="DOCF136" href="#FOOT136"><sup>136</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">random-in-range low high</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">range </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> high low</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> low </span><span class="opn">(</span><span class="pln">random range</span><span class="clo">))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e6"></a>Exercise 3.6:</strong> It is useful to be able to reset a
random-number generator to produce a sequence starting from a given value.
Design a new <code>rand</code> procedure that is called with an argument that is
either the symbol <code>generate</code> or the symbol <code>reset</code> and behaves as
follows: <code>(rand 'generate)</code> produces a new random number; <code>((rand
'reset) ⟨<var>new-value</var>⟩)</code> resets the internal state variable to the
designated <code>⟨</code><var>new-value</var><code>⟩</code>.  Thus, by resetting the state, one can generate
repeatable sequences.  These are very handy to have when testing and debugging
programs that use random numbers.
</p></blockquote>

<a id="g_t3_002e1_002e3"></a>
<a id="The-Costs-of-Introducing-Assignment"></a>
<h4 class="subsection"><span class="secnum">3.1.3</span><span class="sectitle">The Costs of Introducing Assignment</span></h4>

<p>As we have seen, the <code>set!</code> operation enables us to model objects that
have local state.  However, this advantage comes at a price.  Our programming
language can no longer be interpreted in terms of the substitution model of
procedure application that we introduced in <a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a>.  Moreover, no
simple model with “nice” mathematical properties can be an adequate framework
for dealing with objects and assignment in programming languages.
</p>
<p>So long as we do not use assignments, two evaluations of the same procedure
with the same arguments will produce the same result, so that procedures can be
viewed as computing mathematical functions.  Programming without any use of
assignments, as we did throughout the first two chapters of this book, is
accordingly known as <a id="index-functional-programming"></a>
<em>functional programming</em>.
</p>
<p>To understand how assignment complicates matters, consider a simplified version
of the <code>make-withdraw</code> procedure of <a href="#g_t3_002e1_002e1">3.1.1</a> that does not
bother to check for an insufficient amount:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-simplified-withdraw balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W </span><span class="opn">(</span><span class="pln">make-simplified-withdraw </span><span class="lit">25</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">W </span><span class="lit">20</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">5</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">W </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">-5</span></i>
</pre></div>

<p>Compare this procedure with the following <code>make-decrementer</code> procedure,
which does not use <code>set!</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-decrementer balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">)))</span></pre></div>

<p><code>Make-decrementer</code> returns a procedure that subtracts its input from a
designated amount <code>balance</code>, but there is no accumulated effect over
successive calls, as with <code>make-simplified-withdraw</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> D </span><span class="opn">(</span><span class="pln">make-decrementer </span><span class="lit">25</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">D </span><span class="lit">20</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">5</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">D </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">15</span></i>
</pre></div>

<p>We can use the substitution model to explain how <code>make-decrementer</code> works.
For instance, let us analyze the evaluation of the expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">make-decrementer </span><span class="lit">25</span><span class="clo">)</span><span class="pln"> </span><span class="lit">20</span><span class="clo">)</span></pre></div>

<p>We first simplify the operator of the combination by substituting 25 for
<code>balance</code> in the body of <code>make-decrementer</code>.  This reduces the
expression to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> amount</span><span class="clo">))</span><span class="pln"> </span><span class="lit">20</span><span class="clo">)</span></pre></div>

<p>Now we apply the operator by substituting 20 for <code>amount</code> in the body of
the <code>lambda</code> expression:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> </span><span class="lit">20</span><span class="clo">)</span></pre></div>

<p>The final answer is 5.
</p>
<p>Observe, however, what happens if we attempt a similar substitution analysis
with <code>make-simplified-withdraw</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">make-simplified-withdraw </span><span class="lit">25</span><span class="clo">)</span><span class="pln"> </span><span class="lit">20</span><span class="clo">)</span></pre></div>

<p>We first simplify the operator by substituting 25 for <code>balance</code> in the
body of <code>make-simplified-withdraw</code>.  This reduces the expression
to<a class="footnote_link" id="DOCF137" href="#FOOT137"><sup>137</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln"> 
   </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> amount</span><span class="clo">))</span><span class="pln"> </span><span class="lit">25</span><span class="clo">)</span><span class="pln">
 </span><span class="lit">20</span><span class="clo">)</span></pre></div>

<p>Now we apply the operator by substituting 20 for <code>amount</code> in the body of
the <code>lambda</code> expression:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">25</span><span class="pln"> </span><span class="lit">20</span><span class="clo">))</span><span class="pln"> </span><span class="lit">25</span></pre></div>

<p>If we adhered to the substitution model, we would have to say that the meaning
of the procedure application is to first set <code>balance</code> to 5 and then
return 25 as the value of the expression.  This gets the wrong answer.  In
order to get the correct answer, we would have to somehow distinguish the first
occurrence of <code>balance</code> (before the effect of the <code>set!</code>)  from the
second occurrence of <code>balance</code> (after the effect of the <code>set!</code>), and
the substitution model cannot do this.
</p>
<p>The trouble here is that substitution is based ultimately on the notion that
the symbols in our language are essentially names for values.  But as soon as
we introduce <code>set!</code> and the idea that the value of a variable can change,
a variable can no longer be simply a name.  Now a variable somehow refers to a
place where a value can be stored, and the value stored at this place can
change.  In <a href="3_002e2.xhtml#g_t3_002e2">3.2</a> we will see how environments play this role of
“place” in our computational model.
</p>
<a id="Sameness-and-change"></a>
<h5 class="subsubheading">Sameness and change</h5>

<p>The issue surfacing here is more profound than the mere breakdown of a
particular model of computation.  As soon as we introduce change into our
computational models, many notions that were previously straightforward become
problematical.  Consider the concept of two things being “the same.”
</p>
<p>Suppose we call <code>make-decrementer</code> twice with the same argument to create
two procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> D1 </span><span class="opn">(</span><span class="pln">make-decrementer </span><span class="lit">25</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> D2 </span><span class="opn">(</span><span class="pln">make-decrementer </span><span class="lit">25</span><span class="clo">))</span></pre></div>

<p>Are <code>D1</code> and <code>D2</code> the same?  An acceptable answer is yes, because
<code>D1</code> and <code>D2</code> have the same computational behavior—each is a
procedure that subtracts its input from 25.  In fact, <code>D1</code> could be
substituted for <code>D2</code> in any computation without changing the result.
</p>
<p>Contrast this with making two calls to <code>make-simplified-withdraw</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W1 </span><span class="opn">(</span><span class="pln">make-simplified-withdraw </span><span class="lit">25</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> W2 </span><span class="opn">(</span><span class="pln">make-simplified-withdraw </span><span class="lit">25</span><span class="clo">))</span></pre></div>

<p>Are <code>W1</code> and <code>W2</code> the same?  Surely not, because calls to <code>W1</code>
and <code>W2</code> have distinct effects, as shown by the following sequence of
interactions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">W1 </span><span class="lit">20</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">5</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">W1 </span><span class="lit">20</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">-15</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">W2 </span><span class="lit">20</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">5</span></i>
</pre></div>

<p>Even though <code>W1</code> and <code>W2</code> are “equal” in the sense that they are
both created by evaluating the same expression, <code>(make-simplified-withdraw
25)</code>, it is not true that <code>W1</code> could be substituted for <code>W2</code> in any
expression without changing the result of evaluating the expression.
</p>
<p>A language that supports the concept that “equals can be substituted for
equals” in an expression without changing the value of the expression is said
to be <a id="index-referentially-transparent"></a>
<em>referentially transparent</em>.  Referential transparency is
violated when we include <code>set!</code> in our computer language.  This makes it
tricky to determine when we can simplify expressions by substituting equivalent
expressions.  Consequently, reasoning about programs that use assignment
becomes drastically more difficult.
</p>
<p>Once we forgo referential transparency, the notion of what it means for
computational objects to be “the same” becomes difficult to capture in a
formal way.  Indeed, the meaning of “same” in the real world that our
programs model is hardly clear in itself.  In general, we can determine that
two apparently identical objects are indeed “the same one” only by modifying
one object and then observing whether the other object has changed in the same
way.  But how can we tell if an object has “changed” other than by observing
the “same” object twice and seeing whether some property of the object
differs from one observation to the next?  Thus, we cannot determine “change”
without some <em>a priori</em> notion of “sameness,” and we cannot determine
sameness without observing the effects of change.
</p>
<p>As an example of how this issue arises in programming, consider the situation
where Peter and Paul have a bank account with $100 in it.  There is a
substantial difference between modeling this as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> peter-acc </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> paul-acc </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="clo">))</span></pre></div>

<p>and modeling it as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> peter-acc </span><span class="opn">(</span><span class="pln">make-account </span><span class="lit">100</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> paul-acc peter-acc</span><span class="clo">)</span></pre></div>

<p>In the first situation, the two bank accounts are distinct.  Transactions made
by Peter will not affect Paul’s account, and vice versa.  In the second
situation, however, we have defined <code>paul-acc</code> to be <em>the same thing</em>
as <code>peter-acc</code>.  In effect, Peter and Paul now have a joint bank account,
and if Peter makes a withdrawal from <code>peter-acc</code> Paul will observe less
money in <code>paul-acc</code>.  These two similar but distinct situations can cause
confusion in building computational models.  With the shared account, in
particular, it can be especially confusing that there is one object (the bank
account) that has two different names (<code>peter-acc</code> and <code>paul-acc</code>);
if we are searching for all the places in our program where <code>paul-acc</code> can
be changed, we must remember to look also at things that change
<code>peter-acc</code>.<a class="footnote_link" id="DOCF138" href="#FOOT138"><sup>138</sup></a>
</p>
<p>With reference to the above remarks on “sameness” and “change,” observe
that if Peter and Paul could only examine their bank balances, and could not
perform operations that changed the balance, then the issue of whether the two
accounts are distinct would be moot.  In general, so long as we never modify
data objects, we can regard a compound data object to be precisely the totality
of its pieces.  For example, a rational number is determined by giving its
numerator and its denominator.  But this view is no longer valid in the
presence of change, where a compound data object has an “identity” that is
something different from the pieces of which it is composed.  A bank account is
still “the same” bank account even if we change the balance by making a
withdrawal; conversely, we could have two different bank accounts with the same
state information.  This complication is a consequence, not of our programming
language, but of our perception of a bank account as an object.  We do not, for
example, ordinarily regard a rational number as a changeable object with
identity, such that we could change the numerator and still have “the same”
rational number.
</p>
<a id="Pitfalls-of-imperative-programming"></a>
<h5 class="subsubheading">Pitfalls of imperative programming</h5>

<p>In contrast to functional programming, programming that makes extensive use of
assignment is known as <a id="index-imperative-programming"></a>
<em>imperative programming</em>.  In addition to
raising complications about computational models, programs written in
imperative style are susceptible to bugs that cannot occur in functional
programs.  For example, recall the iterative factorial program from 
<a href="1_002e2.xhtml#g_t1_002e2_002e1">1.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter product counter</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter n</span><span class="clo">)</span><span class="pln">
        product
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>Instead of passing arguments in the internal iterative loop, we could adopt a
more imperative style by using explicit assignment to update the values of the
variables <code>product</code> and <code>counter</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">product </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">counter </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter n</span><span class="clo">)</span><span class="pln">
          product
          </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> product </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter 
                                  product</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> counter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">iter</span><span class="clo">))))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">iter</span><span class="clo">)))</span></pre></div>

<p>This does not change the results produced by the program, but it does introduce
a subtle trap.  How do we decide the order of the assignments?  As it happens,
the program is correct as written.  But writing the assignments in the opposite
order
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> counter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> product </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">))</span></pre></div>

<p>would have produced a different, incorrect result.  In general, programming
with assignment forces us to carefully consider the relative orders of the
assignments to make sure that each statement is using the correct version of
the variables that have been changed.  This issue simply does not arise in
functional programs.<a class="footnote_link" id="DOCF139" href="#FOOT139"><sup>139</sup></a>
</p>
<p>The complexity of imperative programs becomes even worse if we consider
applications in which several processes execute concurrently.  We will return
to this in <a href="3_002e4.xhtml#g_t3_002e4">3.4</a>.  First, however, we will address the issue of
providing a computational model for expressions that involve assignment, and
explore the uses of objects with local state in designing simulations.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e7"></a>Exercise 3.7:</strong> Consider the bank account objects
created by <code>make-account</code>, with the password modification described in
<a href="#Exercise-3_002e3">Exercise 3.3</a>.  Suppose that our banking system requires the ability to
make joint accounts.  Define a procedure <code>make-joint</code> that accomplishes
this.  <code>Make-joint</code> should take three arguments.  The first is a
password-protected account.  The second argument must match the password with
which the account was defined in order for the <code>make-joint</code> operation to
proceed.  The third argument is a new password.  <code>Make-joint</code> is to create
an additional access to the original account using the new password.  For
example, if <code>peter-acc</code> is a bank account with password
<code>open-sesame</code>, then
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> paul-acc
  </span><span class="opn">(</span><span class="pln">make-joint peter-acc 
              </span><span class="lit">'open-sesame</span><span class="pln"> 
              </span><span class="lit">'rosebud</span><span class="clo">))</span></pre></div>

<p>will allow one to make transactions on <code>peter-acc</code> using the name
<code>paul-acc</code> and the password <code>rosebud</code>.  You may wish to modify your
solution to <a href="#Exercise-3_002e3">Exercise 3.3</a> to accommodate this new feature.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e8"></a>Exercise 3.8:</strong> When we defined the evaluation
model in <a href="1_002e1.xhtml#g_t1_002e1_002e3">1.1.3</a>, we said that the first step in evaluating an
expression is to evaluate its subexpressions.  But we never specified the order
in which the subexpressions should be evaluated (e.g., left to right or right
to left).  When we introduce assignment, the order in which the arguments to a
procedure are evaluated can make a difference to the result.  Define a simple
procedure <code>f</code> such that evaluating 
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>will return 0 if
the arguments to <code>+</code> are evaluated from left to right but will return 1 if
the arguments are evaluated from right to left.
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT129"><p><a class="footnote_backlink" href="#DOCF129"><sup>129</sup></a>
Actually, this is not quite
true.  One exception was the random-number generator in <a href="1_002e2.xhtml#g_t1_002e2_002e6">1.2.6</a>.
Another exception involved the operation/type tables we introduced in 
<a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a>, where the values of two calls to <code>get</code> with the same
arguments depended on intervening calls to <code>put</code>.  On the other hand,
until we introduce assignment, we have no way to create such procedures
ourselves.</p>
</div>
<div id="FOOT130"><p><a class="footnote_backlink" href="#DOCF130"><sup>130</sup></a>
The value of
a <code>set!</code> expression is implementation-dependent.  <code>Set!</code> should be
used only for its effect, not for its value.
</p>
<p>The name <code>set!</code> reflects a naming convention used in Scheme: Operations
that change the values of variables (or that change data structures, as we will
see in <a href="3_002e3.xhtml#g_t3_002e3">3.3</a>) are given names that end with an exclamation point.
This is similar to the convention of designating predicates by names that end
with a question mark.</p>
</div>
<div id="FOOT131"><p><a class="footnote_backlink" href="#DOCF131"><sup>131</sup></a>
We have already
used <code>begin</code> implicitly in our programs, because in Scheme the body of a
procedure can be a sequence of expressions.  Also, the <code>⟨</code><var>consequent</var><code>⟩</code> part
of each clause in a <code>cond</code> expression can be a sequence of expressions
rather than a single expression.</p>
</div>
<div id="FOOT132"><p><a class="footnote_backlink" href="#DOCF132"><sup>132</sup></a>
In programming-language jargon, the variable
<code>balance</code> is said to be <a id="index-encapsulated"></a>
<em>encapsulated</em> within the
<code>new-withdraw</code> procedure.  Encapsulation reflects the general
system-design principle known as the <a id="index-hiding-principle"></a>
<em>hiding principle</em>: One can make a
system more modular and robust by protecting parts of the system from each
other; that is, by providing information access only to those parts of the
system that have a “need to know.”</p>
</div>
<div id="FOOT133"><p><a class="footnote_backlink" href="#DOCF133"><sup>133</sup></a>
In contrast with
<code>new-withdraw</code> above, we do not have to use <code>let</code> to make
<code>balance</code> a local variable, since formal parameters are already local.
This will be clearer after the discussion of the environment model of
evaluation in <a href="3_002e2.xhtml#g_t3_002e2">3.2</a>.  (See also <a href="3_002e2.xhtml#Exercise-3_002e10">Exercise 3.10</a>.)</p>
</div>
<div id="FOOT134"><p><a class="footnote_backlink" href="#DOCF134"><sup>134</sup></a>
One common way to implement
<code>rand-update</code> is to use the rule that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is updated to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>b</mi>
  </mrow>
</math> 
modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math> are appropriately chosen
integers.  Chapter 3 of <a href="References.xhtml#Knuth-1981">Knuth 1981</a> includes an extensive discussion of
techniques for generating sequences of random numbers and establishing their
statistical properties.  Notice that the <code>rand-update</code> procedure computes
a mathematical function: Given the same input twice, it produces the same
output.  Therefore, the number sequence produced by <code>rand-update</code>
certainly is not “random,” if by “random” we insist that each number in the
sequence is unrelated to the preceding number.  The relation between “real
randomness” and so-called <a id="index-pseudo_002drandom"></a>
<em>pseudo-random</em> sequences, which are
produced by well-determined computations and yet have suitable statistical
properties, is a complex question involving difficult issues in mathematics and
philosophy.  Kolmogorov, Solomonoff, and Chaitin have made great progress in
clarifying these issues; a discussion can be found in <a href="References.xhtml#Chaitin-1975">Chaitin 1975</a>.</p>
</div>
<div id="FOOT135"><p><a class="footnote_backlink" href="#DOCF135"><sup>135</sup></a>
This theorem is due to
E. Cesàro.  See section 4.5.2 of <a href="References.xhtml#Knuth-1981">Knuth 1981</a> for a discussion and a proof.</p>
</div>
<div id="FOOT136"><p><a class="footnote_backlink" href="#DOCF136"><sup>136</sup></a>
<abbr>MIT</abbr> Scheme provides such a procedure.  If
<code>random</code> is given an exact integer (as in <a href="1_002e2.xhtml#g_t1_002e2_002e6">1.2.6</a>) it returns
an exact integer, but if it is given a decimal value (as in this exercise) it
returns a decimal value.</p>
</div>
<div id="FOOT137"><p><a class="footnote_backlink" href="#DOCF137"><sup>137</sup></a>
We don’t substitute for the occurrence of <code>balance</code> in the
<code>set!</code> expression because the <code>⟨</code><var>name</var><code>⟩</code> in a <code>set!</code> is not
evaluated.  If we did substitute for it, we would get <code>(set! 25 (- 25
amount))</code>, which makes no sense.</p>
</div>
<div id="FOOT138"><p><a class="footnote_backlink" href="#DOCF138"><sup>138</sup></a>
The phenomenon of a single computational object
being accessed by more than one name is known as <a id="index-aliasing"></a>
<em>aliasing</em>.  The joint
bank account situation illustrates a very simple example of an alias.  In
<a href="3_002e3.xhtml#g_t3_002e3">3.3</a> we will see much more complex examples, such as “distinct”
compound data structures that share parts.  Bugs can occur in our programs if
we forget that a change to an object may also, as a “side effect,” change a
“different” object because the two “different” objects are actually a
single object appearing under different aliases.  These so-called
<a id="index-side_002deffect-bugs"></a>
<em>side-effect bugs</em> are so difficult to locate and to analyze that some
people have proposed that programming languages be designed in such a way as to
not allow side effects or aliasing (<a href="References.xhtml#Lampson-et-al_002e-1981">Lampson et al. 1981</a>; 
<a href="References.xhtml#Morris-et-al_002e-1980">Morris et al. 1980</a>).</p>
</div>
<div id="FOOT139"><p><a class="footnote_backlink" href="#DOCF139"><sup>139</sup></a>
In view of this, it is ironic that introductory
programming is most often taught in a highly imperative style.  This may be a
vestige of a belief, common throughout the 1960s and 1970s, that programs that
call procedures must inherently be less efficient than programs that perform
assignments.  (<a href="References.xhtml#Steele-1977">Steele 1977</a> debunks this argument.)  Alternatively it may
reflect a view that step-by-step assignment is easier for beginners to
visualize than procedure call.  Whatever the reason, it often saddles beginning
programmers with “should I set this variable before or after that one”
concerns that can complicate programming and obscure the important ideas.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="3_002e2.xhtml#g_t3_002e2" accesskey="n" rel="next">3.2</a>, Prev: <a href="Chapter-3.xhtml#Chapter-3" accesskey="p" rel="prev">Chapter 3</a>, Up: <a href="#g_t3_002e1" accesskey="u" rel="prev">3.1</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>